
Solutions
1. T (n) = 3T (n/2) + n
2
=⇒ T (n) = Θ(n
2
) (Case 3)
2. T (n) = 4T (n/2) + n
2
=⇒ T (n) = Θ(n
2
log n) (Case 2)
3. T (n) = T (n/2) + 2
n
=⇒ Θ(2
n
) (Case 3)
4. T (n) = 2
n
T (n/2) + n
n
=⇒ Does not apply (a is not constant)
5. T (n) = 16T (n/4) + n =⇒ T (n) = Θ(n
2
) (Case 1)
6. T (n) = 2T (n/2) + n log n =⇒ T (n) = n log
2
n (Case 2)
7. T (n) = 2T (n/2) + n/ log n =⇒ Do e s not apply (non-polynomial difference between f (n) and n
log
b
a
)
8. T (n) = 2T (n/4) + n
0.51
=⇒ T (n) = Θ(n
0.51
) (Case 3)
9. T (n) = 0.5T (n/2) + 1/n =⇒ Does not apply (a < 1)
10. T (n) = 16T (n/4) + n! =⇒ T (n) = Θ(n!) (Case 3)
11. T (n) =
√
2T (n/2) + log n =⇒ T (n) = Θ(
√
n) (Case 1)
12. T (n) = 3T (n/ 2) + n =⇒ T (n) = Θ(n
lg 3
) (Case 1)
13. T (n) = 3T (n/ 3) +
√
n =⇒ T (n) = Θ(n) (Case 1)
14. T (n) = 4T (n/ 2) + cn =⇒ T (n) = Θ(n
2
) (Case 1)
15. T (n) = 3T (n/ 4) + n log n =⇒ T (n) = Θ(n log n) (Ca se 3)
16. T (n) = 3T (n/ 3) + n/2 =⇒ T (n) = Θ(n log n) (Case 2)
17. T (n) = 6T (n/ 3) + n
2
log n =⇒ T (n) = Θ(n
2
log n) (Case 3)
18. T (n) = 4T (n/ 2) + n/ log n =⇒ T (n) = Θ (n
2
) (Case 1)
19. T (n) = 64T (n/8) − n
2
log n =⇒ Does not apply (f (n) is not positive)
20. T (n) = 7T (n/ 3) + n
2
=⇒ T (n) = Θ(n
2
) (Case 3)
21. T (n) = 4T (n/ 2) + log n =⇒ T (n) = Θ(n
2
) (Case 1)
22. T (n) = T (n/ 2) + n(2 − cos n) =⇒ Does not apply. We are in Case 3, but the regularity condition is
violated. (Consider n = 2 πk, where k is odd and arbitrarily large. For any such choice of n, you can
show that c ≥ 3/2, thereby violating the re gularity condition.)
3